package leetcode.code0799;

import leetcode.IDebug;

//执行用时：111 ms, 在所有 Java 提交中击败了5.19%的用户
//
//内存消耗：42.4 MB, 在所有 Java 提交中击败了5.84%的用户
//
//通过测试用例：312 / 312
public class Solution2 implements IDebug {
	int poured;

	public double champagneTower(int poured, int query_row, int query_glass) {
		this.poured = poured;
		Double[][][] dp = new Double[100][100][2];
		return this.champagneTower(query_row, query_glass, dp)[1];
	}

	private double[] champagneTower(int row, int glass, Double[][][] dp) {
		if (row == 0 && glass == 0) {
			double out = Math.max(0, this.poured - 1);
			double ans = Math.min(1, this.poured);
			return new double[] { out, ans };
		}
		if (dp[row][glass][0] != null) {
			return new double[] { dp[row][glass][0], dp[row][glass][1] };
		}
		if (glass == 0) {
			double[] ret = this.champagneTower(row - 1, glass, dp);
			double p = 1d * ret[0] / 2;
			return new double[] { Math.max(0, p - 1), Math.min(1, p) };
		}
		if (glass == row) {
			double[] ret = this.champagneTower(row - 1, glass - 1, dp);
			double p = 1d * ret[0] / 2;
			return new double[] { Math.max(0, p - 1), Math.min(1, p) };
		}
		double[] ret1 = this.champagneTower(row - 1, glass - 1, dp);
		double[] ret2 = this.champagneTower(row - 1, glass, dp);
		double p = 1d * ret1[0] / 2 + 1d * ret2[0] / 2;
		dp[row][glass][0] = Math.max(0, p - 1);
		dp[row][glass][1] = Math.min(1, p);
		return new double[] { dp[row][glass][0], dp[row][glass][1] };
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
